
from functools import lru_cache

memo:dict[int,int] = {0:0,1:1}

def fib2(n:int) -> int:
    print(f"fib2 {n}")
    if n<2:
        return n
    return fib2(n-2)+fib2(n-1)

def fib3(n:int) -> int:
    if n not in memo:
        memo[n] = fib3(n-2)+fib3(n-1)
    return memo[n]

@lru_cache(maxsize=None)
def fib4(n:int) -> int:
    if n<2:
        return n
    return fib4(n-2)+fib4(n-1)

def fib5(n:int) -> int:
    if n == 0:
        return 0
    last: int = 0
    next: int = 1
    for _ in range(1,n):
        last,next = next, last+next
    return next

if __name__ == "__main__":
    print(fib2(5))

    print(fib3(20))

    print(fib4(20))

    print(fib5(20))